package A一周刷爆LeetCode.A基础班.F二叉树;

import java.util.LinkedList;

/**
 * @author wei.zhao
 * @description: 二叉树的序列化和反序列化
 * @date 2022年02月28日 18:13
 */
public class Code12_SerializeAndReconstructTree {

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);
        head.left.left.left = new Node(8);
        head.right.right.right = new Node(9);
        head.right.right.right.left= new Node(10);
        System.out.print("宽度优先遍历结果：");
        Code03_WidthTraversal.widthTraversal(head);
        String s = serializeTree(head);
        System.out.println("序列化结果：" + s);
        System.out.print("TreeNode优先遍历结果：");
        Code03_WidthTraversal.widthTraversal(reconstructTree(s));
    }

    // 序列化
    public static String serializeTree(Node head) {
        String result = "[";
        LinkedList<Node> list = new LinkedList<>();
        if (head != null) {
            list.add(head);
            result += head.value;
        }
        while (!list.isEmpty()) {
            Node pop = list.pop();
            if (pop.left != null) {
                result += "," + pop.left.value;
                list.add(pop.left);
            } else {
                result += "," + "null";
            }
            if (pop.right != null) {
                result += "," + pop.right.value;
                list.add(pop.right);
            } else {
                result += "," + "null";
            }
        }
        result += "]";
        return result;
    }

    //反序列化
    public static Node reconstructTree(String str) {
        str = str.substring(1, str.length() - 1);
        if (str.length() == 0) {
            return null;
        }
        String[] strings = str.split(",");
        LinkedList<String> valueList = new LinkedList<>();
        for (int i = 1; i < strings.length; i++) {
            valueList.add(strings[i]);
        }
        Node head = new Node(Integer.valueOf(strings[0]));
        LinkedList<Node> nodeList = new LinkedList<>();
        nodeList.add(head);
        while (!valueList.isEmpty()) {
            Node pop = nodeList.pop();
            String value1 = valueList.pop();
            if (!value1.equals("null")) {
                Node treeNode = new Node(Integer.valueOf(value1));
                pop.left = treeNode;
                nodeList.add(treeNode);
            }
            String value2 = valueList.pop();
            if (!value2.equals("null")) {
                Node treeNode = new Node(Integer.valueOf(value2));
                pop.right = treeNode;
                nodeList.add(treeNode);
            }
        }
        return head;
    }


}
